package main

import "fmt"

/*
1、介绍
快速排序是对冒泡排序的一种改进。基本思想是：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小
然后再按此方法对着两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
2、实例
要求：对[-9 78 0 23 -567 70]进行从小到大排序，要求使用快速排序

*/
//left表示数组左边的下标
//right表示数组右边的下标
//array表示要排序的数组
func QuickSort(left int, right int, arr *[6]int) {
	l := left
	r := right
	//pivot是中轴，支点
	pivot := arr[(left+right)/2]
	temp := 0
	//for循环的目标是将比pivot小的数放到左边
	//比pivot大的数放到右边
	for l < r {
		//先从pivot的左边找到大于等于pivot的值
		for arr[l] < pivot {
			l++
		}
		//从pivot的右边找到小于等于pivot的值
		for arr[r] > pivot {
			r--
		}
		//l>=r表明本次分解任务完成，break
		if l >= r {
			break
		}
		//交换
		temp = arr[l]
		arr[l] = arr[r]
		arr[r] = temp
		//优化
		// if arr[l] == pivot {
		// 	r--
		// }
		// if arr[r] == pivot {
		// 	l++
		// }
	}
	//如果l==r，再移动一位，相等的时候指向了pivot
	if l == r {
		l++
		r--
	}
	//向左递归
	if left < r {
		QuickSort(left, r, arr)
	}
	//向右递归
	if right > l {
		QuickSort(l, right, arr)
	}
}
func main() {
	arr := [6]int{-9, 78, 0, 23, -567, 70}
	QuickSort(0, 5, &arr)

	fmt.Printf("arr=%v", arr)
}
